package Sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

public class ShellSort {

  public static void main(String[] args) {
    int num[] = new int[]{8,9,1,7,2,3,5,4,6,0};
//    shellSort(num);//交换式
//    shellSort2(num);//移位式
//    int num[] = new int[80000];
//    for (int i = 0; i < 80000; i++) {
//      num[i] = (int)(Math.random()*80000);//生成一个0到80000的数
//    }
//    测试插入排序的效率
    Date date = new Date();
    SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy--MM-dd HH:mm:ss");
    String dateStr1 = simpleDateFormat.format(date);
    System.out.println("排序前的时间：" + dateStr1);

//    排序后
    shellSort2(num);

    Date date2 = new Date();
    String dateStr2 = simpleDateFormat.format(date2);
    System.out.println("排序后的时间：" + dateStr2);
  }

//  交换式
  public static void shellSort(int[] num) {

    int temp = 0;
    for (int gap = num.length/2; gap >= 1 ; gap = gap/2) {//增量
      for (int i = gap; i < num.length ; i = i + gap) {//将数组分成gap组
        for (int j = i - gap; j >= 0 ; j = j - gap) {
          if (num[j] > num[j + gap]){
            temp = num[j];
            num[j] = num[j + gap];
            num[j+gap] = temp;
          }
        }
      }
      System.out.println("排序的结果：" + Arrays.toString(num));
    }
    System.out.println("排序的结果：" + Arrays.toString(num));
  }

//  移位式
  public static void shellSort2(int[] arr) {
    /*
    8,9,1,7,2,3,5,4,6,0
     */

    for (int gap = arr.length/2; gap >= 1 ; gap = gap/2) {
//      从第gap个元素开始，直接进行插入排序
      for (int i = gap; i < arr.length; i++) {
        int j = i;
        int temp = arr[j];
        if (arr[i] < arr[j - gap]){
          while (j - gap >= 0 && temp < arr[j- gap]){
            arr[j] = arr[j - gap];
            j = j - gap;
          }
          arr[j] = temp;
        }
      }
    }
//    System.out.println("排序的结果：" + Arrays.toString(arr));
  }
}
